package top.fengleifeng.question;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: leetcode-test
 * @description: 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：m = 2, n = 3, k = 1
 * 输出：3
 * 示例 2：
 * <p>
 * 输入：m = 3, n = 1, k = 0
 * 输出：1
 * 提示：
 * <p>
 * 1 <= n,m <= 100
 * 0 <= k <= 20
 * 通过次数64,040提交次数127,551
 * 在真实的面试中遇到过这道题？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author: fengleifeng
 * @create: 2020-09-07 11:52
 **/
public class Y剑指Offer13机器人的运动范围 {
    /**
     * 广度优先
     */
    class Solution {
        public int movingCount(int m, int n, int k) {
            //
            int reuslt = 1;
            boolean[][] map = new boolean[m][n];
            map[0][0] = true;
            Queue<int[]> queue = new LinkedList<>();
            queue.add(new int[]{0, 0});
            int[][] position = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            while (queue.size() != 0) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int[] one = queue.poll();
                    int x = one[0];
                    int y = one[1];

                    for (int j = 0; j < position.length; j++) {
                        int[] positionOne = position[j];
                        int positionOneX = positionOne[0];
                        int positionOneY = positionOne[1];
                        int newX = x + positionOneX;
                        int newY = y + positionOneY;

                        if (newX < 0 || newY < 0 || newX >= m || newY >= n || map[newX][newY]) {
                            continue;
                        }
                        map[newX][newY] = true;
                        int sum = getData(newX, newY);
                        if (sum <= k) {
                            queue.add(new int[]{newX,newY});
                            reuslt++;
                        }
                    }
                }
            }
            return reuslt;
        }


        //计算两个坐标和
        public int getData(int x, int y) {
            int sum = 0;
            while (x != 0) {
                sum += x % 10;
                x = x / 10;
            }
            while (y != 0) {
                sum += y % 10;
                y = y / 10;
            }
            return sum;
        }
    }

    public static void main(String[] args) {
        int m = 7;
        int n = 2;
        int k = 3;
        int i = new Y剑指Offer13机器人的运动范围().new Solution().movingCount(m, n, k);
        System.out.println(i);
    }
}
